"""
难度：中等
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
（即先从左往右，再从右往左进行下一层遍历，
以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100
"""

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        self.dfs(root,0,ans)
        return list(map(list,ans))        
    def dfs(self, root, l, ans):
        if not root:
            return
        if len(ans) == l:
            ans.append(collections.deque())
        if l % 2 == 0:
            ans[l].append(root.val)
        else:
            ans[l].appendleft(root.val)
        if root.left:
            self.dfs(root.left, l+1, ans)
        if root.right:
            self.dfs(root.right, l+1, ans)